package 子串

/*
原题链接:
https://leetcode.cn/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

B站 帅地玩编程
剑指offer 59_1.滑动窗口的最大值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，
他们的最大值分别为{4,4,6,6,6,5}；

针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个：
{[2,3,4],2,6,2,5,1}，
{2,[3,4,2],6,2,5,1}，
{2,3,[4,2,6],2,5,1}，
{2,3,4,[2,6,2],5,1}，
{2,3,4,2,[6,2,5],1}，
{2,3,4,2,6,[2,5,1]}。

思路:

k=3
准备一个队列:  放那些可能成为最大值的元素的下标

-3		3下标
-1      2下标
3		1下标

1		0下标   出队列

参数数组:
1 3 -1 -3 -4 3 6 7
|
| |
| | |

	|  |  |
	   |  |  |

先构成滑动窗口, 同时元素1进队列
然后放入3, 由于3比队列头部的元素要大, 那么需要将3之前, 队列所有的元素弹出
因为在当前滑动窗口范围内, 肯定是这个3会成为最大值

先构成滑动窗口, 同时元素1进队列
然后放入3, 由于3比队列头部的元素大, 那么需要将3之前, 队列所有的元素弹出
因为再当前滑动窗口范围内, 肯定是这个3会成为最大值

然后放入-1, 比队列头部元素小, 头部元素不需要出队, 并且构成滑动窗口长度,
当前窗口范围最大值, 就是队首的元素值

继续遍历元素, 队列放入-3, 比栈顶元素要小, 直接加入即可
继续遍历元素, 队列放入-4, 比栈顶元素要小, 直接加入即可, 但是栈顶元素下标, 已经超过当前滑动窗口的范围, 需要将队首元素剔除
即: 队尾元素下标 - k == 队首元素下标
*/
func maxSlidingWindow(nums []int, k int) []int {
	if nums == nil || len(nums) <= 1 { // 特殊判断
		return nums
	}

	st := make([]int, 0)              // 初始化队列
	res := make([]int, len(nums)-k+1) // 初始化结果数组
	index := 0

	for i := 0; i < len(nums); i++ { //遍历所有元素
		// 如果队列不是空的 && 队列的队尾元素 < 当前元素，那么就需要不断出栈
		for len(st) > 0 && nums[st[len(st)-1]] <= nums[i] {
			st = st[:len(st)-1] // 删除队尾元素
		}

		st = append(st, i) // 加入队列
		if i-k == st[0] {  // 如果栈顶的元素不在滑动窗口范围内了，直接出栈
			st = st[1:]
		}

		if i+1 >= k { // 能组成滑动窗口长度后，就不断添加最大值
			res[index] = nums[st[0]]
			index++
		}
	}

	return res
}
